home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / inet / ien / ien-137 < prev    next >
Text File  |  1988-12-01  |  36KB  |  817 lines

  1.  
  2. IEN 137                                                      Danny Cohen
  3.                                                              U S C/I S I
  4.                                                             1 April 1980
  5.  
  6.  
  7.                    ON HOLY WARS AND A PLEA FOR PEACE
  8.  
  9.  
  10.  
  11.                               INTRODUCTION
  12.  
  13.  
  14. This  is  an  attempt to stop a war.  I hope it is not too late and that
  15. somehow, magically perhaps, peace will prevail again.
  16.  
  17. The latecomers into the arena believe that the issue is:  "What  is  the
  18. proper byte order in messages?".
  19.  
  20. The root of the conflict lies much deeper than that.  It is the question
  21. of  which  bit  should  travel first, the bit from the little end of the
  22. word, or the bit from the big end of the  word?  The  followers  of  the
  23. former  approach are called the Little-Endians, and the followers of the
  24. latter are called the Big-Endians.  The details of the holy war  between
  25. the  Little-Endians  and  the  Big-Endians  are  documented  in  [6] and
  26. described, in brief, in the Appendix. I recommend that you  read  it  at
  27. this point.
  28.  
  29. The  above  question  arises  from  the  serialization  process which is
  30. performed on messages in order to send them through communication media.
  31. If the communication unit is a message - these problems have no meaning.
  32. If the units are computer "words" then one may ask in which order  these
  33. words  are sent, what is their size, but not in which order the elements
  34. of these words are sent, since they are sent virtually  "at-once".    If
  35. the unit of transmission is an 8-bit byte, similar questions about bytes
  36. are  meaningful,  but  not  the  order of the elementary particles which
  37. constitute these bytes.
  38.  
  39. If the units of communication  are  bits,  the  "atoms"  ("quarks"?)  of
  40. computation,  then  the  only  meaningful question is the order in which
  41. bits are sent.
  42.  
  43. Obviously, this is actually the case  for  serial  transmission.    Most
  44. modern  communication  is  based  on  a  single  stream  of  information
  45. ("bit-stream").  Hence, bits, rather than bytes or words, are the  units
  46. of  information  which  are  actually transmitted over the communication
  47. channels such as wires and satellite connections.
  48.  
  49. Even though a great deal of effort, in both hardware  and  software,  is
  50. dedicated  to  giving  the appearance of byte or word communication, the
  51. basic fact remains:  bits are communicated.
  52.  
  53. Computer memory may be viewed as a linear sequence of bits, divided into
  54. bytes, words, pages and so on.  Each unit  is  a  subunit  of  the  next
  55. level.  This is, obviously, a hierarchical organization.
  56.                                    2
  57.  
  58. If  the  order  is  consistent, then such a sequence may be communicated
  59. successfully while both parties maintain their freedom to treat the bits
  60. as a set of groups of any arbitrary size.  One party may treat a message
  61. as a "page", another as so many "words", or so many "bytes" or  so  many
  62. bits.    If  a  consistent  bit order is used, the "chunk-size" is of no
  63. consequence.
  64.  
  65. If an inconsistent bit order is used, the chunk size must be  understood
  66. and  agreed  upon  by all parties.  We will demonstrate some popular but
  67. inconsistent orders later.
  68.  
  69. In a consistent order, the bit-order, the  byte-order,  the  word-order,
  70. the  page-order, and all the other higher level orders are all the same.
  71. Hence, when considering a serial bit-stream, along a communication  line
  72. for example, the "chunk" size which the originator of that stream has in
  73. mind is not important.
  74.  
  75. There  are  two  possible  consistent  orders.  One is starting with the
  76. narrow end of each  word  (aka  "LSB")  as  the  Little-Endians  do,  or
  77. starting with the wide end (aka "MSB") as their rivals, the Big-Endians,
  78. do.
  79.  
  80. In  this note we usually use the following sample numbers: a "word" is a
  81. 32-bit quantity and is designated by a "W", and a  "byte"  is  an  8-bit
  82. quantity  which  is  designated  by  a  "C"  (for "Character", not to be
  83. confused with "B" for "Bit)".
  84.  
  85.  
  86.  
  87.  
  88.                               MEMORY ORDER
  89.  
  90. The first  word  in  memory  is  designated  as  W0,  by  both  regimes.
  91. Unfortunately, the harmony goes no further.
  92.  
  93. The Little-Endians assign B0 to the LSB of the words and B31 is the MSB.
  94. The Big-Endians do just the opposite, B0 is the MSB and B31 is the LSB.
  95.  
  96. By  the  way,  if  mathematicians had their way, every sequence would be
  97. numbered from ZERO up, not from ONE, as is traditionally done.   If  so,
  98. the first item would be called the "zeroth"....
  99.  
  100. Since  most  computers  are not built by mathematicians, it is no wonder
  101. that some computers designate  bits  from  B1  to  B32,  in  either  the
  102. Little-Endians'  or the Big-Endians' order.  These people probably would
  103. like to number their words from W1 up, just to be consistent.
  104.  
  105. Back to the main theme.  We would like to illustrate the  hierarchically
  106. consistent  order  graphically,  but  first  we have to decide about the
  107. order  in  which  computer  words are written on paper.  Do they go from
  108. left to right, or from right to left?
  109.                                    3
  110.  
  111. The English language, like most modern languages, suggests that  we  lay
  112. these computer words on paper from left to right, like this:
  113.  
  114.                  |---word0---|---word1---|---word2---|....
  115.  
  116. In  order  to  be  consistent,  B0 should be to the left of B31.  If the
  117. bytes in a word are designated as C0 through C3 then C0 is also  to  the
  118. left of C3.  Hence we get:
  119.  
  120.                  |---word0---|---word1---|---word2---|....
  121.                  |C0,C1,C2,C3|C0,C1,C2,C3|C0,C1,C2,C3|.....
  122.                  |B0......B31|B0......B31|B0......B31|......
  123.  
  124. If  we  also  use  the  traditional  convention,  as  introduced  by our
  125. numbering system, the wide-end is on the left and the narrow-end  is  on
  126. the right.
  127.  
  128. Hence, the above is a perfectly consistent view of the world as depicted
  129. by  the  Big-Endians.    Significance  consistency decreases as the item
  130. numbers (address) increases.
  131.  
  132. Many computers share with the Big-Endians this view  about  order.    In
  133. many  of  their  diagrams the registers are connected such that when the
  134. word W(n) is shifted right, its LSB moves into the MSB of word W(n+1).
  135.  
  136. English text strings are stored  in  the  same  order,  with  the  first
  137. character in C0 of W0, the next in C1 of W0, and so on.
  138.  
  139. This order is very consistent with itself and with the English language.
  140.  
  141. On  the  other  hand,  the  Little-Endians  have  their  view,  which is
  142. different but also self-consistent.
  143.  
  144. They believe that one should start with the narrow end  of  every  word,
  145. and  that  low  addresses  are  of  lower  order  than  high  addresses.
  146. Therefore they put their words on paper  as  if  they  were  written  in
  147. Hebrew, like this:
  148.  
  149.                    ...|---word2---|---word1---|---word0---|
  150.  
  151. When they add the bit order and the byte order they get:
  152.  
  153.                    ...|---word2---|---word1---|---word0---|
  154.                   ....|C3,C2,C1,C0|C3,C2,C1,C0|C3,C2,C1,C0|
  155.                  .....|B31......B0|B31......B0|B31......B0|
  156.  
  157. In  this regime, when word W(n) is shifted right, its LSB moves into the
  158. MSB of word W(n-1).
  159.                                    4
  160.  
  161. English  text  strings  are  stored  in  the  same order, with the first
  162. character in C0 of W0, the next in C1 of W0, and so on.
  163.  
  164. This order is very consistent with itself, with the Hebrew language, and
  165. (more importantly) with mathematics, because significance increases with
  166. increasing item numbers (address).
  167.  
  168. It has the disadvantage that English  character  streams  appear  to  be
  169. written backwards; this is only an aesthetic problem but, admittedly, it
  170. looks funny, especially to speakers of English.
  171.  
  172. In  order  to  avoid  receiving  strange  comments about this orders the
  173. Little-Endians pretend that they are Chinese, and write the  bytes,  not
  174. right-to-left but top-to-bottom, like:
  175.  
  176.                         C0: "J"
  177.                         C1: "O"
  178.                         C2: "H"
  179.                         C3: "N"
  180.                         ..etc..
  181.  
  182. Note that there is absolutely no specific significance whatsoever to the
  183. notion  of  "left"  and  "right" in bit order in a computer memory.  One
  184. could think about it as "up" and "down" for example,  or  mirror  it  by
  185. systematically  interchanging  all  the  "left"s and "right"s.  However,
  186. this notion  stems  from  the  concept  that  computer  words  represent
  187. numbers,  and from the old mathematical tradition that the wide-end of a
  188. number (aka the MSB) is called "left" and the narrow-end of a number  is
  189. called "right".
  190.  
  191. This mathematical convention is the point of reference for the notion of
  192. "left" and "right".
  193.  
  194. It  is  easy to determine whether any given computer system was designed
  195. by Little-Endians or by Big-Endians.  This is done by watching  the  way
  196. the  registers  are connected for the "COMBINED-SHIFT" operation and for
  197. multiple-precision arithmetic like integer products;  also  by  watching
  198. how  these  quantities  are  stored in memory; and obviously also by the
  199. order in which bytes are stored within words.  Don't let  the  B0-to-B31
  200. direction  fool  you!!  Most computers were designed by Big-Endians, who
  201. under the threat of criminal prosecution pretended to be Little-Endians,
  202. rather than seeking exile in  Blefuscu.    They  did  it  by  using  the
  203. B0-to-B31   convention   of   the   Little-Endians,  while  keeping  the
  204. Big-Endians' conventions for bytes and words.
  205.  
  206. The PDP10 and the 360, for example, were designed by Big-Endians:  their
  207. bit  order, byte-order, word-order and page-order are the same. The same
  208. order also  applies  to  long  (multi-word)  character  strings  and  to
  209. multiple precision numbers.
  210.  
  211.                                    5
  212.  
  213. Next,  let's consider the new M68000 microprocessor.  Its way of storing
  214. a 32-bit number, xy, a 16-bit number, z, and the string  "JOHN"  in  its
  215. 16-bit words is shown below (S = sign bit, M = MSB, L = LSB):
  216.  
  217.         SMxxxxxxx yyyyyyyyL SMzzzzzzL  "J" "O"   "H" "N"
  218.        |--word0--|--word1--|--word2--|--word3--|--word4--|....
  219.        |-C0-|-C1-|-C0-|-C1-|-C0-|-C1-|-C0-|-C1-|-C0-|-C1-|.....
  220.        |B15....B0|B15....B0|B15....B0|B15....B0|B15....B0|......
  221.  
  222. The  M68000  always  has on the left (i.e., LOWER byte- or word-address)
  223. the wide-end of numbers in any of the various sizes which it may use:  4
  224. (BCD), 8, 16 or 32 bits.
  225.  
  226. Hence,  the  M68000  is  a  consistent  Big-Endian,  except  for its bit
  227. designation, which is used to camouflage its  true  identity.  Remember:
  228. the Big-Endians were the outlaws.
  229.  
  230. Let's  look next at the PDP11 order, since this is the first computer to
  231. claim to be a Little-Endian. Let's again look at the way data is  stored
  232. in memory:
  233.  
  234.                "N" "H"   "O" "J"  SMzzzzzzL SMyyyyyyL SMxxxxxxL
  235.          ....|--word4--|--word3--|--word2--|--word1--|--word0--|
  236.         .....|-C1-|-C0-|-C1-|-C0-|-C1-|-C0-|-C1-|-C0-|-C1-|-C0-|
  237.        ......|B15....B0|B15....B0|B15....B0|B15....B0|B15....B0|
  238.  
  239. The  PDP11  does  not  have  an instruction to move 32-bit numbers.  Its
  240. multiplication products  are  32-bit  quantities  created  only  in  the
  241. registers,  and  may  be  stored  in  memory in any way.  Therefore, the
  242. 32-bit quantity, xy, was not shown in the above diagram.
  243.  
  244. Hence, the above order is a Little-Endians' consistent order.  The PDP11
  245. always stores on the  left  (i.e.,  HIGHER  bit-  or  byte-address)  the
  246. wide-end of numbers of any of the sizes which it may use:  8 or 16 bits.
  247.  
  248. However,  due to some infiltration from the other camp, the registers of
  249. this Little-Endian's marvel are  treated  in  the  Big-Endians'  way:  a
  250. double  length  operand  (32-bit)  is  placed  with its MSB in the lower
  251. address register and the LSB in the higher  address  register.    Hence,
  252. when depicted on paper, the registers have to be put from left to right,
  253. with  the  wide  end  of  numbers  in  the LOWER-address register.  This
  254. affects the integer multiplication and division, the combined-shifts and
  255. more. Admittedly, Blefuscu scores on this one.
  256.  
  257. Later, floating-point hardware was introduced for the PDP11/45.
  258.  
  259. Floating-point  numbers  are  represented  by  either  32-   or   64-bit
  260. quantities,  which are 2 or 4 PDP11 words.  The wide end is the one with
  261. the sign bit(s), the exponent and the MSB of the  fraction.  The  narrow
  262. end is the one with the LSB of the fraction.  On paper these formats are
  263. clearly shown with the wide end on the left and the narrow on the right,
  264. according  to  the centuries old mathematical conventions.  On page 12-3
  265.                                    6
  266.  
  267. of  the  PDP11/45  processor  handbook,  [3],  there is a cute graphical
  268. demonstration of this order, with the word "FRACTION" split over all the
  269. 2 or the 4 words which are used to store it.
  270.  
  271. However, due to some oversights in the security screening  process,  the
  272. Blefuscuians  took  over,  again.  They assigned, as they always do, the
  273. wide end to the LOWer addresses in memory, and the narrow to the  HIGHer
  274. addresses.
  275.  
  276. Let   "xy"   and  "abcd"  be  32-  and  64-bit  floating-point  numbers,
  277. respectively.  Let's look how these numbers are stored in memory:
  278.  
  279.           ddddddddL ccccccccc bbbbbbbbb SMaaaaaaa yyyyyyyyL SMxxxxxxx
  280.      ....|--word5--|--word4--|--word3--|--word2--|--word1--|--word0--|
  281.     .....|-C1-|-C0-|-C1-|-C0-|-C1-|-C0-|-C1-|-C0-|-C1-|-C0-|-C1-|-C0-|
  282.    ......|B15....B0|B15....B0|B15....B0|B15....B0|B15....B0|B15....B0|
  283.  
  284. Well, Blefuscu scores many points for this. The above reference  in  [3]
  285. does not even try to camouflage it by any Chinese notation.
  286.  
  287. Encouraged by this success, as minor as it is, the Blefuscuians tried to
  288. pull  another fast one.  This time it was on the VAX, the sacred machine
  289. which all the Little-Endians worship.
  290.  
  291. Let's look at the VAX order. Again, we look at the way  the  above  data
  292. (with xy being a 32-bit integer) is stored in memory:
  293.  
  294.                "N" "H"   "O" "J"  SMzzzzzzL SMxxxxxxx yyyyyyyyL
  295.           ...ng2-------|-------long1-------|-------long0-------|
  296.          ....|--word4--|--word3--|--word2--|--word1--|--word0--|
  297.         .....|-C1-|-C0-|-C1-|-C0-|-C1-|-C0-|-C1-|-C0-|-C1-|-C0-|
  298.        ......|B15....B0|B15....B0|B15....B0|B15....B0|B15....B0|
  299.  
  300. What a beautifully consistent Little-Endians' order this is !!!
  301.  
  302. So,  what  about  the infiltrators? Did they completely fail in carrying
  303. out their mission?  Since the integer  arithmetic  was  closely  guarded
  304. they  attacked  the  floating  point  and the double-floating which were
  305. already known to be easy prey.
  306.                                    7
  307.  
  308. Let's  look, again, at the way the above data is stored, except that now
  309. the 32-bit quantity xy is a floating point  number:  now  this  data  is
  310. organized in memory in the following Blefuscuian way:
  311.  
  312.                "N" "H"   "O" "J"  SMzzzzzzL yyyyyyyyL SMxxxxxxx
  313.           ...ng2-------|-------long1-------|-------long0-------|
  314.          ....|--word4--|--word3--|--word2--|--word1--|--word0--|
  315.         .....|-C1-|-C0-|-C1-|-C0-|-C1-|-C0-|-C1-|-C0-|-C1-|-C0-|
  316.        ......|B15....B0|B15....B0|B15....B0|B15....B0|B15....B0|
  317.  
  318. Blefuscu  scores  again.    The  VAX  is  found guilty, however with the
  319. explanation that it tries to be compatible with the PDP11.
  320.  
  321. Having found themselves there, the  VAXians  found  a  way  around  this
  322. unaesthetic   appearance:  the  VAX  literature  (e.g.,  p. 10  of  [4])
  323. describes this order by using the Chinese top-to-bottom notation, rather
  324. than an embarrassing left-to-right or right-to-left one.  This page is a
  325. marvel.  One has to admire the skillful way in which some quantities are
  326. shown in columns 8-bit wide, some in 16 and other in 32, all in order to
  327. avoid the egg-on-the-face problem.....
  328.  
  329. By the way, some engineering-type people complain  about  the  "Chinese"
  330. (vertical)  notation  because usually the top (aka "up") of the diagrams
  331. corresponds to "low"-memory (low addresses).  However,  anyone  who  was
  332. brought  up by computer scientists, rather than by botanists, knows that
  333. trees grow downward, having their roots at the top of the page and their
  334. leaves down below. Computer scientists seldom remember  which  way  "up"
  335. really is (see 2.3 of [5], pp. 305-309).
  336.  
  337. Having   scored   so  easily  in  the  floating  point  department,  the
  338. Blefuscuians moved to new territories: Packed-Decimal.  The VAX is  also
  339. capable of using 4-bit-chunk decimal arithmetic, which is similar to the
  340. well known BCD format.
  341.  
  342. The  Big-Endians struck again, and without any resistance got their way.
  343. The decimal number 12345678 is stored in the VAX memory in this order:
  344.  
  345.                            7 8  5 6  3 4  1 2
  346.                       ...|-------long0-------|
  347.                      ....|--word1--|--word0--|
  348.                     .....|-C1-|-C0-|-C1-|-C0-|
  349.                    ......|B15....B0|B15....B0|
  350.  
  351. This ugliness cannot be hidden even by the standard Chinese trick.
  352.                                    8
  353.  
  354.  
  355.  
  356.  
  357.  
  358.                  SUMMARY (of the Memory-Order section)
  359.  
  360.  
  361. To  the best of my knowledge only the Big-Endians of Blefuscu have built
  362. systems with a consistent order  which  works  across  chunk-boundaries,
  363. registers,   instructions   and   memories.      I   failed  to  find  a
  364. Little-Endians' system which is totally consistent.
  365.  
  366.  
  367.  
  368.  
  369.                            TRANSMISSION ORDER
  370.  
  371.  
  372. In either of the consistent orders the first bit (B0) of the first  byte
  373. (C0)  of the first word (W0) is sent first, then the rest of the bits of
  374. this byte, then (in the same order) the rest of the bytes of this  word,
  375. and so on.
  376.  
  377. Such  a sequence of 8 32-bit words, for example, may be viewed as either
  378. 4 long-words, 8 words, 32 bytes or 256 bits.
  379.  
  380. For example, some people treat the ARPA-internet-datagrams as a sequence
  381. of 16-bit words whereas others treat them as either 8-bit  byte  streams
  382. or  sequences  of  32-bit  words.    This  has  never  been  a source of
  383. confusion, because the Big-Endians' consistent order has been assumed.
  384.  
  385. There are many ways to devise inconsistent orders.  The two most popular
  386. ones are the following and its mirror image.  Under this order the first
  387. bit to be sent is the LEAST significant bit (B0) of the MOST significant
  388. byte (C0) of the first word, followed by the rest of the  bits  of  this
  389. byte,  then  the  same  right-to-left bit order inside the left-to-right
  390. byte order.
  391.  
  392. Figure 1 shows the transmission  order  for  the  4  orders  which  were
  393. discussed above, the 2 consistent and the 2 inconsistent ones.
  394.  
  395. Those who use such an inconsistent order (or any other), and only those,
  396. have  to  be  concerned with the famous byte-order problem.  If they can
  397. pretend that their communication medium is really a  byte-oriented  link
  398. then this inconsistency can be safely hidden under the rug.
  399.  
  400. A  few  years ago 8-bit microprocessors appeared and changed drastically
  401. the way we do business.  A few years  later  a  wide  variety  of  8-bit
  402. communication  hardware  (e.g., Z80-SIO and 2652) followed, all of which
  403. operate in the Little-Endians' order.
  404.                                    9
  405.  
  406. Now   a  wave  of  16-bit  microprocessors  has  arrived.    It  is  not
  407. inconceivable that 16-bit communication hardware will become  a  reality
  408. relatively soon.
  409.  
  410. Since  the  16-bit communication gear will be provided by the same folks
  411. who brought us the 8-bit communication gear, it is safe to expect  these
  412. two modes to be compatible with each other.
  413.  
  414. The  only  way to achieve this is by using the consistent Little-Endians
  415. order, since all the existing gear is already in Little-Endians order.
  416.  
  417. We have already observed that the Little-Endians do not have  consistent
  418. memory orders for intra-computer organization.
  419.  
  420. IF  the 16-bit communication link could be made to operate in any order,
  421. consistent or not, which would give it the appearance of being  a  byte-
  422. oriented link, THEN the Big-Endians could push (ask? hope? pray?) for an
  423. order  which transmits the bytes in left-to-right (i.e., wide-end first)
  424. and use that as a basis for transmitting all quantities (except BCD)  in
  425. the  more  convenient  Big-Endians  format,  with  the  most significant
  426. portions  leading  the  least  significant,  maintaining   compatibility
  427. between 16- and 32-bit communication, and more.
  428.  
  429. However, this is a big "IF".
  430.  
  431. Wouldn't  it  be nice if we could encapsulate the byte-communication and
  432. forget all about the idiosyncrasies of the past, introduced by RS232 and
  433. TELEX, of sending the narrow-end first?
  434.  
  435. I believe that it would be nice, but  nice  things  do  not  necessarily
  436. occur, especially if there is so much silicon against them.
  437.  
  438. Hence,  our  choice now is between (1) Big-Endians' computer-convenience
  439. and (2) future compatibility between  communication  gear  of  different
  440. chunk size.
  441.  
  442. I believe that this is the question, and we should address it as such.
  443.  
  444. Short  term  convenience  considerations are in favor of the former, and
  445. the long term ones are in favor of the latter.
  446.  
  447. Since  the  war  between  the  Little-Endians  and  the  Big-Endians  is
  448. imminent, let's count who is in whose camp.
  449.  
  450. The founders of the Little-Endians party are RS232 and TELEX, who stated
  451. that  the  narrow-end  is  sent  first.  So  do  the  HDLC  and the SDLC
  452. protocols, the Z80-SIO, Signetics-2652,  Intel-8251,  Motorola-6850  and
  453. all  the  rest  of  the  existing communication devices.  In addition to
  454. these protocols and chips the PDP11s and the VAXes have already  pledged
  455. their allegiance to this camp, and deserve to be on this roster.
  456.                                    10
  457.  
  458. The HDLC protocol is a full fledged member of this camp because it sends
  459. all  of its fields with the narrow end first, as is specifically defined
  460. in Table 1/X.25 (Frame formats) in section 2.2.1 of  Recommendation X.25
  461. (see [2]).  A close examination of this table reveals that the bit order
  462. of  transmission  is  always  1-to-8.  Always, except the FCS (checksum)
  463. field, which is the only 16-bit quantity in the byte-oriented protocol.
  464.  
  465. The FCS is sent in the 16-to-1 order.  How did the  Blefuscuians  manage
  466. to  pull  off  such a fiasco?!  The answer is beyond me.  Anyway, anyone
  467. who designates bits as 1-to-8 (instead of 0-to-7) must  be  gullible  to
  468. such tricks.
  469.  
  470. The Big-Endians have the PDP10's, 370's, ALTO's and Dorado's...
  471.  
  472. An  interesting  creature  is the ARPANet-IMP.  The documentation of its
  473. standard host interface (aka "LH/DH") states that "The high order bit of
  474. each word is  transmitted  first"  (p. 4-4  of  [1]),  hence,  it  is  a
  475. Big-Endian.    This  is very convenient, and causes no confusion between
  476. diagrams which are either 32- (e.g., on p. 3-25) and 16-bit wide  (e.g.,
  477. on p. 5-14).
  478.  
  479. However, the IMP's Very Distant Host (VDH) interface is a Little-Endian.
  480.  
  481. The  same  document  ([1],  again,  p. F-18), states that the data "must
  482. consist of an even number of 8-bit bytes. Further, considering each pair
  483. of bytes as a 16-bit word, the less significant  (right)  byte  is  sent
  484. first".
  485.  
  486. In  order  to make this even more clear, p. F-23 states "All bytes (data
  487. bytes too) are transmitted least significant (rightmost) bit first".
  488.  
  489. Hence, both camps may claim to have this schizophrenic  double-agent  in
  490. their camp.
  491.  
  492. Note  that  the  Lilliputians'  camp  includes  all the who's-who of the
  493. communication world, unlike the Blefuscuians' camp which  is  very  much
  494. oriented toward the computing world.
  495.  
  496. Both  camps  have  already  adopted  the  slogan "We'd rather fight than
  497. switch!".
  498.  
  499. I believe they mean it.
  500.                                    11
  501.  
  502.  
  503.  
  504.  
  505.  
  506.               SUMMARY (of the Transmission-Order section)
  507.  
  508.  
  509. There  are two camps each with its own language.  These languages are as
  510. compatible with each other as any Semitic and Latin languages are.
  511.  
  512. All Big-Endians can talk to each other with relative ease.
  513.  
  514. So can all the Little-Endians, even though there  are  some  differences
  515. among the dialects used by different tribes.
  516.  
  517. There is no middle ground. Only one end can go first.
  518.  
  519.  
  520.  
  521.  
  522.                                CONCLUSION
  523.  
  524.  
  525. Each  camp  tries  to convert the other.  Like all the religious wars of
  526. the past, logic is not the decisive tool. Power is.  This  holy  war  is
  527. not the first one, and probably will not be the last one either.
  528.  
  529. The  "Be reasonable, do it my way" approach does not work.  Neither does
  530. the Esperanto approach of "let's all switch to yet a new language".
  531.  
  532. Our communication world may split according to the  language  used.    A
  533. certain  book  (which  is  NOT  mentioned in the references list) has an
  534. interesting story about a similar phenomenon, the Tower of Babel.
  535.  
  536. Little-Endians are Little-Endians and Big-Endians  are  Big-Endians  and
  537. never the twain shall meet.
  538.  
  539. We  would like to see some Gulliver standing up between the two islands,
  540. forcing a unified communication regime on all of us.  I do hope that  my
  541. way  will  be chosen, but I believe that, after all, which way is chosen
  542. does not make too much difference.  It is more important to  agree  upon
  543. an order than which order is agreed upon.
  544.  
  545. How about tossing a coin ???
  546.                                    12
  547.  
  548.  
  549.                           time          time
  550.                             |           |
  551.            \                |           |                /
  552.             \               |           |               /
  553.              \              |           |              /
  554.               \             |           |             /
  555.                \            |           |            /
  556.                 \           |           |           /
  557.                  \          |           |          /
  558.                   \         |           |         /
  559.                    \        |           |        /
  560.                     \       |           |       /
  561.                      \      |           |      /
  562.                       \     |           |     /
  563.                        \    |           |    /
  564.                         \   |           |   /
  565.                          \  |           |  /
  566.                           \ |           | /
  567.        <-MSB---------------LSB-       -MSB---------------LSB->
  568.                order (1)    |           |    order (2)
  569.  
  570.  
  571.                           time         time
  572.                             |           |
  573.             /               |           |               \
  574.            /                |           |                \
  575.               /             |           |             \
  576.              /              |           |              \
  577.                 /           |           |           \
  578.                /            |           |            \
  579.                   /         |           |         \
  580.                  /          |           |          \
  581.                     /       |           |       \
  582.                    /        |           |        \
  583.                       /     |           |     \
  584.                      /      |           |      \
  585.                         /   |           |   \
  586.                        /    |           |    \
  587.                           / |           | \
  588.                          /  |           |  \
  589.        <-MSB---------------LSB-       -MSB---------------LSB->
  590.                order (3)    |           |    order (4)
  591.  
  592.  
  593.  
  594.  
  595.  Figure 1: Possible orders, consistent: (1)+(2), inconsistent: (3)+(4).
  596.  
  597.                                    13
  598.  
  599.                             A P P E N D I X
  600.  
  601.  
  602.  
  603. Some notes on Swift's Gulliver's Travels:
  604.  
  605.  
  606. Gulliver finds out that there is a law, proclaimed by the grandfather of
  607. the  present  ruler,  requiring  all citizens of Lilliput to break their
  608. eggs only at the little ends.  Of course, all those citizens  who  broke
  609. their  eggs at the big ends were angered by the proclamation.  Civil war
  610. broke out between the Little-Endians and the Big-Endians,  resulting  in
  611. the  Big-Endians  taking  refuge  on  a  nearby  island,  the kingdom of
  612. Blefuscu.
  613.  
  614. Using Gulliver's unquestioning point of view, Swift satirizes  religious
  615. wars.    For  11,000  Lilliputian  rebels  to  die over a controversy as
  616. trivial as at which end eggs have to be broken seems not only cruel  but
  617. also  absurd,  since Gulliver is sufficiently gullible to believe in the
  618. significance  of  the  egg  question.    The  controversy  is  important
  619. ethically  and  politically  for the Lilliputians.  The reader may think
  620. the issue is silly, but he should consider what Swift is making  fun  of
  621. the actual causes of religious- or holy-wars.
  622.  
  623. In  political  terms,  Lilliput  represents England and Blefuscu France.
  624. The religious  controversy  over  egg-breaking  parallels  the  struggle
  625. between  the  Protestant  Church  of  England and the Catholic Church of
  626. France, possibly referring to some differences about what the Sacraments
  627. really mean.  More specifically,  the  quarrel  about  egg-breaking  may
  628. allude  to  the  different  ways that the Anglican and Catholic Churches
  629. distribute communion, bread and wine for the Anglican, but  bread  alone
  630. for  the  Catholic.   The French and English struggled over more mundane
  631. questions as well, but in this part of Gulliver's Travels, Swift  points
  632. up  the  symbolic  difference  between  the  churches  to  ridicule  any
  633. religious war.
  634.  
  635.  
  636.     For ease of reference please note that Lilliput  and  Little-Endians
  637.     both start with an "L", and that both Blefuscu and Big-Endians start
  638.     with a "B".  This is handy while reading this note.
  639.                                    14
  640.  
  641.                           R E F E R E N C E S
  642.  
  643.  
  644.  
  645. [1]   Bolt Beranek & Newman.
  646.       Report No. 1822: Interface Message Processor.
  647.       Technical Report, BB&N, May, 1978.
  648.  
  649. [2]   CCITT.
  650.       Orange Book. Volume VIII.2:  Public Data Networks.
  651.       International Telecommunication Union, Geneva, 1977.
  652.  
  653. [3]   DEC.
  654.       PDP11 04/05/10/35/40/45 processor handbook.
  655.       Digital Equipment Corp., 1975.
  656.  
  657. [4]   DEC.
  658.       VAX11 - Architecture Handbook.
  659.       Digital Equipment Corp., 1979.
  660.  
  661. [5]   Knuth, D. E.
  662.       The Art of Computer Programming. Volume I:  Fundamental
  663.          Algorithms.
  664.       Addison-Wesley, 1968.
  665.  
  666. [6]   Swift, Jonathan.
  667.       Gulliver's Travel.
  668.       Unknown publisher, 1726.
  669.                                    15
  670.  
  671.                OTHER SLIGHTLY RELATED TOPICS (IF AT ALL)
  672.  
  673.  
  674.                not necessarily for inclusion in this note
  675.  
  676.  
  677.  
  678.  
  679.  
  680. Who's on first?   Zero or One ??
  681.  
  682. People  start  counting  from  the  number  ONE.  The very word FIRST is
  683. abbreviated into the symbol "1st" which indicates ONE,  but  this  is  a
  684. very modern notation.  The older notions do not necessarily support this
  685. relationship.
  686.  
  687. In  English  and  French - the word "first" is not derived from the word
  688. "one" but from an  old  word  for  "prince"  (which  means  "foremost").
  689. Similarly,  the  English  word  "second"  is not derived from the number
  690. "two" but from an old word which means "to follow".  Obviously there  is
  691. an  close  relation between "third" and "three", "fourth" and "four" and
  692. so on.
  693.  
  694. Similarly, in Hebrew, for example, the word "first" is derived from  the
  695. word  "head",  meaning  "the foremost", but not specifically No. 1.  The
  696. Hebrew word for "second" is specifically derived from  the  word  "two".
  697. The same for three, four and all the other numbers.
  698.  
  699. However,  people have,for a very long time, counted from the number One,
  700. not from Zero.  As a  matter  of  fact,  the  inclusion  of  Zero  as  a
  701. full-fledged  member  of  the  set of all numbers is a relatively modern
  702. concept.
  703.  
  704. Zero is one of the most important numbers mathematically.  It  has  many
  705. important properties, such as being a multiple of any integer.
  706.  
  707. A  nice mathematical theorem states that for any basis, b, the first b^N
  708. (b to the Nth power) positive integers  are  represented  by  exactly  N
  709. digits  (leading zeros included).  This is true if and only if the count
  710. starts with Zero (hence, 0 through b^N-1), not with One (for  1  through
  711. b^N).
  712.  
  713. This theorem is the basis of computer memory addressing.  Typically, 2^N
  714. cells  are  addressed by an N-bit addressing scheme.  Starting the count
  715. from One, rather than Zero, would cause either the loss  of  one  memory
  716. cell,  or  an  additional  address  line.    Since  either  price is too
  717. expensive, computer engineers agree to use the mathematical notation  of
  718. starting with Zero.  Good for them!
  719.  
  720. The  designers  of  the 1401 were probably ashamed to have address-0 and
  721. hid it from the users, pretending that the memory started at address-1.
  722.                                    16
  723.  
  724. This  is  probably the reason that all memories start at address-0, even
  725. those of systems which count bits from B1 up.
  726.  
  727. Communication engineers, like most "normal" people, start counting  from
  728. the  number One.  They never suffer by having to lose a memory cell, for
  729. example.  Therefore, they are happily counting 1-to-8, and not 0-to-7 as
  730. computer people learn to do.
  731.  
  732.  
  733.  
  734. ORDER OF NUMBERS.
  735.  
  736. In English, we write numbers  in  Big-Endians'  left-to-right  order.  I
  737. believe  that  this is because we SAY numbers in the Big-Endians' order,
  738. and because we WRITE English in Left-to-right order.
  739.  
  740. Mathematically there is a lot to be said for the Little-Endians' order.
  741.  
  742. Serial comparators and dividers prefer the former.   Serial  adders  and
  743. multipliers prefer the latter order.
  744.  
  745. When was the common Big-Endians order adopted by most modern languages?
  746.  
  747. In  the  Bible,  numbers  are  described  in words (like "seven") not by
  748. digits (like "7") which were "invented" nearly a  thousand  years  after
  749. the  Bible  was  written.  In  the  old  Hebrew  Bible  many numbers are
  750. expressed in the  Little-Endians  order  (like  "Seven  and  Twenty  and
  751. Hundred") but many are in the Big-Endians order as well.
  752.  
  753. Whenever  the  Bible is translated into English the contemporary English
  754. order is used.  For example, the above number appears in that  order  in
  755. the  Hebrew  source  of  The  Book  of  Esther (1:1).  In the King James
  756. Version it is (in English) "Hundred and  Seven  and  Twenty".    In  the
  757. modern  Revised  American  Standard  Version of the Bible this number is
  758. simply "One Hundred and Twenty-Seven".
  759.  
  760.  
  761.  
  762. INTEGERS vs. FRACTIONS
  763.  
  764. Computer designers treat fix-point multiplication in one of two ways, as
  765. an integer-multiplication or as a fractional-multiplication.
  766.  
  767. The reason is that when two 16-bit numbers, for example, are multiplied,
  768. the result is a 31-bit number in a 32-bit field.    Integers  are  right
  769. justified;  fractions are left justified.  The entire difference is only
  770. a single 1-bit shift.    As  small  as  it  is,  this  is  an  important
  771. difference.
  772.  
  773. Hence,   computers   are   wired   differently   for   these   kinds  of
  774. multiplications.  The addition/subtraction operation  is  the  same  for
  775. either integer/fraction operation.
  776.                              17
  777.  
  778. If  the  LSB  is  B0  then the value of a number is SIGMA<B(i)*[(2)^i]>,
  779. for i=0,15, in the above example.  This is, obviously, an integer.
  780.  
  781. If the MSB is B0 then the value of a  number  is  SIGMA<B(i)*[(1/2)^i]>,
  782. for i=0,15.  This is, obviously, a fraction.
  783.  
  784. Hence, after multiplication the Integerites would typically keep B0-B15,
  785. the  LSH  (Least Significant Half), and discard the MSH, after verifying
  786. that there is no overflow into it.  The  Fractionites  would  also  keep
  787. B0-B15, which is the MSH, and discard the LSH.
  788.  
  789. One  could  expect Integerites to be Little-Endians, and Fractionites to
  790. be Big-Endians.  I do not believe that the world is that consistent.
  791.  
  792.  
  793.  
  794. SWIFT's POINT
  795.  
  796. It may be interesting to notice that  the  point  which  Jonathan  Swift
  797. tried  to  convey  in  Gulliver's Travels in exactly the opposite of the
  798. point of this note.
  799.  
  800. Swift's point is that the difference between breaking  the  egg  at  the
  801. little-end  and  breaking  it  at the big-end is trivial.  Therefore, he
  802. suggests, that everyone does it in his own preferred way.
  803.  
  804. We agree that the difference between sending eggs with  the  little-  or
  805. the  big-end first is trivial, but we insist that everyone must do it in
  806. the same way, to avoid anarchy.  Since the difference is trivial we  may
  807. choose either way, but a decision must be made.
  808.  
  809.  
  810.  
  811.  
  812.  
  813.  
  814.  
  815.  
  816.  
  817.